package com.yequan.leetcode.greedy.canReach_1306;

import java.util.LinkedList;

/**
 * @author yequan
 * @date 2022/03/02 08:23
 **/
public class CanReach {

    /**
     * 广度优先算法
     */
    public boolean canReach1(int[] arr, int start) {
        int length = arr.length;
        boolean[] visited = new boolean[length];
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            Integer currentIndex = queue.poll();
            if (currentIndex + arr[currentIndex] < length && !visited[currentIndex + arr[currentIndex]]) {
                visited[currentIndex + arr[currentIndex]] = true;
                queue.offer(currentIndex + arr[currentIndex]);
                if (arr[currentIndex + arr[currentIndex]] == 0) {
                    return true;
                }
            }
            if (currentIndex - arr[currentIndex] >= 0 && !visited[currentIndex - arr[currentIndex]]) {
                visited[currentIndex - arr[currentIndex]] = true;
                queue.offer(currentIndex - arr[currentIndex]);
                if (arr[currentIndex - arr[currentIndex]] == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 深度优先算法
     */
    public boolean canReach2(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        return dfs1(arr, start, visited);
    }

    public boolean dfs1(int[] arr, int currentIndex, boolean[] visited) {
        if (currentIndex < 0 || currentIndex >= arr.length) {
            return false;
        }
        if (arr[currentIndex] == 0) {
            return true;
        }
        if (visited[currentIndex]) {
            return false;
        } else {
            visited[currentIndex] = true;
        }
        return dfs1(arr, currentIndex + arr[currentIndex], visited) || dfs1(arr, currentIndex - arr[currentIndex], visited);
    }

    public boolean canReach3(int[] arr, int start) {
        int length = arr.length;
        boolean[] visited = new boolean[length];
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            Integer currentIndex = queue.poll();
            if (currentIndex + arr[currentIndex] < length && !visited[currentIndex + arr[currentIndex]]) {
                visited[currentIndex + arr[currentIndex]] = true;
                queue.offer(currentIndex + arr[currentIndex]);
                if (arr[currentIndex + arr[currentIndex]] == 0) {
                    return true;
                }
            }
            if (currentIndex - arr[currentIndex] >= 0 && !visited[currentIndex - arr[currentIndex]]) {
                visited[currentIndex - arr[currentIndex]] = true;
                queue.offer(currentIndex - arr[currentIndex]);
                if (arr[currentIndex - arr[currentIndex]] == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean canReach4(int[] arr, int start) {
        int length = arr.length;
        boolean[] visited = new boolean[length];
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            Integer currentIndex = queue.poll();
            if (currentIndex + arr[currentIndex] < length && !visited[currentIndex + arr[currentIndex]]) {
                visited[currentIndex + arr[currentIndex]] = true;
                queue.offer(currentIndex + arr[currentIndex]);
                if (arr[currentIndex + arr[currentIndex]] == 0) {
                    return true;
                }
            }
            if (currentIndex - arr[currentIndex] >= 0 && !visited[currentIndex - arr[currentIndex]]) {
                visited[currentIndex - arr[currentIndex]] = true;
                queue.offer(currentIndex - arr[currentIndex]);
                if (arr[currentIndex - arr[currentIndex]] == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean canReach5(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        return dfs2(arr, start, visited);
    }

    public boolean dfs2(int[] arr, int currentIndex, boolean[] visited) {
        if (currentIndex < 0 || currentIndex >= arr.length) {
            return false;
        }
        if (arr[currentIndex] == 0) {
            return true;
        }
        if (visited[currentIndex]) {
            return false;
        } else {
            visited[currentIndex] = true;
        }
        return dfs2(arr, currentIndex + arr[currentIndex], visited) || dfs2(arr, currentIndex - arr[currentIndex], visited);
    }

}
